Міністерство освіти і науки України
Національний університет «Львівська політехніка»
кафедра САПР
ЗВІТ
до лабораторної роботи №5
на тему:
«Контекстно вільні граматики. Зав’язок контекстно вільної граматики і автомата з магазинною пам’яттю»
з курсу:
«Лінгвістичне забезпечення САПР»
Львів 2010
МЕТА РОБОТИ
Вивчити особливості використання контекстно вільних граматик та їх зв'язок з автоматами з магазинною пам’яттю.
ЛАБОРАТОРНЕ ЗАВДАННЯ
Побудувати дерево виводу, сформувати КВ-граматику і розробити МП-автомат для наступної мови:
21. (a+b)/c*a
ХІД РОБОТИ
1. Побудова дерева виводу.
*
<І >
2. Формування КВ-граматики.
G=(VT, VN, , P).
VT={a, b, c, +, /, * , (, )};
VN={S, V, M, N, І, O};
=S
3. Побудова МП-автомата
Q={S1, S2};
Σ={a, b, c, +, /, *, ¬};
Г={ S, V, M, І, O, a, b, c, +, /, *, (, ), };
δ
q0=S1;
Z0=;
F=ДОПУСТИТИ;
Таблиці станів:
S1
a
b
c
+
/
*
(
)
¬
S
S1,ТР., S→ІOІOV
V
S2, ТР., V→)M(
M
S1, ТР., M→ІOІ
О
S1, ТР., O→+
S2,ТР.,
O→/
S2,ТР.,
O→*
І
S1, ТР., І→a
S2, ТР.,
І→a
S2,ТР.,
І→b
S2,ТР.,
І→c
S2
a
b
c
+
/
*
(
)
¬
a
S1,Зсув Вишт.
b
S2,Зсув Вишт.
c
S1,Зсув Вишт.
+
S1,Зсув Вишт.
/
S1,Зсув Вишт.
*
S1,Зсув Вишт.
(
S1,Зсув Вишт.
)
S1,Зсув Вишт.
ДОП.
ТЕКСТ ПРОГРАМИ
import java.util.*;
import java.io.*;
class Magazine {
public byte size = 20;
public byte startedQuantityOfMagazine = 2;
private char[] mag = new char[size];
private byte i, p;
public byte s;
public int f;//F(0 - не допуск, 1 - допуск)
public String str;
public Magazine(String str) {
this.str = str;
s = 1; f = -1;
mag[0] = '^'; p++;
mag[1] = 'S'; p++;
for (i = 3; i < size - 1; i++)
{
mag[i] = ' ';
}
}
public void push(char c)
{
if (p == size - 1)
{
System.out.println("Magazine is full.");
}
else
{
mag[p] = c; p++;
}
}
public void pop()
{
p--;
mag[p] = ' ';
}
public void printAllMagazine()
{
for (int i=0; i<p; i++){
System.out.print(mag[i]);
}
}
public char HeadOfMagazine()
{
return mag[p - 1];
}
public byte tablesOFStanes()
{
byte x=0;
switch(this.s) {
case 1:
if (HeadOfMagazine() == 'S' && str.charAt(0) == '(')
{
x = 1;
pop();
push('I'); push('O'); push('I'); push('O'); push('V');
}
else if (HeadOfMagazine() == 'V' && str.charAt(0) == '(')
{
x = 1;
pop();
push(')'); push('M'); push('(');
this.s = 2;
}
else if (HeadOfMagazine() == 'M' && str.charAt(0) == 'a')
{
x = 1;
pop();
push('I'); push('O'); push('I');
}
else if (HeadOfMagazine() == 'I' && str.charAt(0) == 'a')
{
x = 1;
pop();
push('a');
this.s = 2;
}
else if (HeadOfMagazine() == 'O' && str.charAt(0) == '+')
{
x = 1;
pop();
push('+');
this.s = 2;
}
else if (HeadOfMagazine() == 'I' && str.charAt(0) == 'b')
{
x = 1;
pop();
push('b');
this.s = 2;
}
else if (HeadOfMagazine() == 'O' && str.charAt(0) == '/')
{
x = 1;
pop();
push('/');
this.s = 2;
}
else if...
